/*
 * @Description  : 快排
 * @Autor        : yanwang
 * @CreateDate   : 2022-02-13 14:04:21
 * @LastEditors  : yanwang
 * @LastEditTime : 2022-02-13 16:42:50
 */

const arr = [5,3,4,6,2,8,7,9,1, 12, 43, 34]
// 简单实现
// l: 左边界
const quick_sort_v1 = function (arr, l, r){
  if(l >= r) return;
  let x = l, y = r; // x: 左指针
  let base = arr[l]; // y: 右指针

  // partition
  while( x < y ) {
    while( x < y && arr[y] >= base) y--; //找到右边比基准小的值

    if(x < y) arr[x] = arr[y]; // 放到左指针的位置。
    x++;

    // if(x < y) arr[x++] = arr[y]; // 放到左指针的位置，左指针往前走一步。

    while(x < y && arr[x] <= base) x++; // 找到左边大于基准的值
    if(x < y) arr[y--] = arr[x]; // 把左侧大于基准的值放到右指针的位置， 右指针往左移动一下
  }
  arr[x] = base; 

  quick_sort_v1(arr, l, x - 1);
  quick_sort_v1(arr, x + 1, r);
} 
quick_sort_v1(arr, 0 , arr.length - 1);

// 单边递归
const quick_sort_v2 = function (arr, l, r){
  if(l >= r) return;
  
  while(l < r) { ////
    let x = l, y = r, base = arr[x];
    while(x < y) {
      while(x < y && arr[y] >= base) y--;
      if(x < y) arr[x++] = arr[y];
      
      while(x < y && arr[x] <= base) x++;
      if(x < y) arr[y--] = arr[x];
    }
    arr[x] = base;

    
    quick_sort_v2(arr, x + 1, r);

    r = x - 1;  ///
  }
}

function median(a, b, c) {
  if(a > b) [a, b] = [b, a];
  if(a > c) [a, c] = [c, a];
  if(b > c) [c, b] = [b, c];
  return b;
}
// 三点取中法 15
const threshold = 3; 
const _quick_sort_v3 = function (arr, l, r){
  while( l - r > threshold) {
    let x = l; y = r; base = median(arr[l], arr[(l + r) >> 1], arr[r]);
    do {
      while(arr[x] < base) x++;
      while(arr[y] > base) y--;
      if(x <= y) {
        [arr[x], arr[y]] = [arr[y], arr[x]];
        x++; y--;
      }

      quick_sort_v3(arr, x , r);
    } while(x <= y)
  }
}

const quick_sort_v3 = function(arr, l, r) {
  _quick_sort_v3(arr, l, r);

  inbsert_sort(arr, l, r);
}

const inbsert_sort = function(arr, l, r) {
  let ind = l; // 最小值

  // 查找最小值， 放到最前面 //// 减少特判
  for(let i = 1; i< r; i++) { // 查找最小值
    if(arr[i] < arr[ind]) ind = i;
  }
  while(ind > l) { // 将最小值移动到最前面
    [arr[ind], arr[ind - 1]] = [arr[ind - 1], arr[ind]]
  }

  for(let i = l + 2; i<=r; i++) {
    let j = i; // i：当前要插入的元素   j: 与当前要插入的元素比较的元素
    while(arr[i] < arr[j - 1]) {
      [arr[i], arr[j - 1]] = [ arr[j-1], arr[i]];
      j--;
    }
  }
}

quick_sort_v3(arr, 0 , arr.length - 1);
console.log(arr);

